package stu.day9_day18;

import java.util.ArrayDeque;

public class LeetCode42 {
    public int trap(int[] height) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int result = 0;
        for(int i=0;i<height.length;i++){
            if(stack.isEmpty()){
                stack.push(i);
            }else if(height[stack.peek()]>=height[i]){
                stack.push(i);
            }else{
                while (!stack.isEmpty()&&height[stack.peek()]<height[i]){
                    int x = stack.pop();

                    if(!stack.isEmpty()&&height[stack.peek()]>height[x]){
                        int y = stack.peek();
                        int gao = Math.min(height[i],height[y])-height[x];
                        int kuan = i-y-1;
                        result += gao*kuan;
                    }
                }
                stack.push(i);
            }
        }
        return result;

    }
}
